This invention relates generally to memory units and more particularly to techniques for accessing memory addresses within such memory units.
The use of electronic memory units is prevalent in many different types of devices. For example, memory is used in general purpose computers where programs and user data are stored in the memory and accessed as necessary by the computer processor. Although general purpose computers may be the most commonly thought of device which uses such memory, many other devices use electronic memory for storing data. For example, mobile telephones, household electronics and handheld entertainment units are just a few of the devices that utilize electronic memory to store data.
As is well known in the art, traditional memory is accessed by providing a memory address to the memory unit and either reading data from or writing data to the particular memory address. One traditional type of memory addressing is base-index addressing in which memory is accessed using a base address b and an index value x. The index x is added to the base address b to calculate the memory address a to be accessed. Such conventional memory addressing is shown in FIG. 1 which illustrates a logical memory 100 which is 64 bits (8 bytes) wide and has capacity to store 256 64-bit data words. Assume for the present illustration that the base value points to the first memory location 102 of logical memory 100. By adding the index value to the base value, the index value acts as an offset and identifies the memory location 104 which has an address of a=b+x. In accordance with conventional memory addressing techniques, the hardware will return the 64 bit data word starting at location 104 to a memory register 106.
Another known technique for accessing memory, as illustrated in FIG. 2, is a block access. In accordance with this technique, rather than accessing a single data word from the memory unit, a contiguous block of data is read starting at the memory location identified using base-index addressing as described above. With reference to FIG. 2, assume that the base plus index calculation (a=b+x) results in an identification of memory address 202. Rather than accessing the 64 bit data word starting at address 202, the block access technique will access a contiguous block of data starting at location 202. The amount of data that will be accessed depends on the particular implementation. For purposes of illustrations, assume that the block access returns three 64 bit data words. As shown in FIG. 2, the block memory access will return the three 64 bit data words starting at memory location 202. Assuming a read operation, the resulting data will be stored either in a register or another memory location, illustrated in FIG. 2 as 206.
One well known type of memory access is a table lookup, in which data to be accessed is stored in memory as a logical table. The table data structure is particularly well suited for base-index addressing, in which the base address represents the starting location of the table and the index represents the particular entry in the table. Table lookups are often used to implement data transformations in cryptographic algorithms in order to save computation time. Rather than calculate such data transformations in real-time, the data transformations are calculated in advance and the results are stored in a memory table. When a transformation is needed, a table lookup is performed and the result is retrieved from the table. While these table lookups substantially improve the efficiency of cryptographic algorithms, the table lookups remain one of the more time consuming tasks. When many data transformations are necessary, there are a large number of table lookups.
One known technique for simplifying multiple table lookups is the use of a technique in which a memory register (e.g., 64 bits) is considered as containing a number of segments each representing table indices. For example, the memory word may be considered as containing eight 8-bit segments each representing a table index. Each segment is considered as a memory index and is added to a base address to identify a memory location. Each memory address is accessed (e.g., read) and the data at each of the accessed memory addresses is then stored, either in a register or in main memory. It is noted that while this technique may be implemented using one processor instruction, each memory access is performed sequentially, with one memory access at a time. Thus, in the illustrative case in which a 64 bit memory word is considered as containing eight 8 bit segments, there would be eight sequential memory accesses.
Table lookups are an important technique in various computer processing tasks. However, main memory table lookups are expensive in terms of processing time and represent a significant amount of processing time for those algorithms (e.g., cryptographic algorithms) which require a large number of table lookups.